#include <iostream>
#include <vector>
#include <string>
#include <Vector.hpp>
using namespace std;

class Solution
{
public:
    vector<string> fullJustify(vector<string> &words, int maxWidth)
    {
        vector<string> res;
        int cur_len = -1;
        int cur_start = 0;
        for (int i = 0; i < words.size(); i++)
        {
            // decide who many words in this line
            if (cur_len + words[i].size() + 1 > maxWidth)
            {
                // put words in line
                int white_space = maxWidth - cur_len;
                int num_spaces = i - cur_start - 1;
                string line;
                if (num_spaces == 0)
                {
                    line.append(words[cur_start]);
                    for (int n = 0; n < white_space; n++)
                        line.push_back(' ');
                }
                else
                {
                    int avr_space = white_space / num_spaces + 1;
                    int extra_space = white_space % num_spaces;
                    for (int j = cur_start; j < i - 1; j++)
                    {
                        line.append(words[j]);
                        for (int n = 0; n < avr_space + (extra_space > 0 ? 1 : 0); n++)
                            line.push_back(' ');
                        extra_space--;
                    }
                    line.append(words[i - 1]);
                }
                res.push_back(line);
                cur_len = -1;
                cur_start = i;
            }
            cur_len += words[i].size() + 1;
        }
        // finish last line
        string line;
        for (int j = cur_start; j < words.size() - 1; j++)
        {
            line.append(words[j]);
            line.push_back(' ');
        }
        line.append(words[words.size() - 1]);
        while (line.size() < maxWidth)
            line.push_back(' ');
        res.push_back(line);
        return res;
    }
};

int main()
{
    cout << "Code68" << endl;
    Solution s;
    // vector<string> words = {"This", "is", "an", "example", "of", "text", "justification."};
    // vector<string> words = {"What", "must", "be", "acknowledgment", "shall", "be"};
    vector<string> words = {"Science", "is", "what", "we", "understand", "well", "enough", "to", "explain",
                            "to", "a", "computer.", "Art", "is", "everything", "else", "we", "do"};
    // vector<string> words = {"ask", "not", "what", "your", "country", "can", "do", "for","you", "ask", "what", "you", "can", "}
    vector<string> res = s.fullJustify(words, 20);
    for (auto &str : res)
        cout << str << ':' << str.size() << endl;
    return 0;
}